package SelectionSort;

import LinearSearch.ArrayGenerator;

import java.util.Arrays;

/**
 * ClassName: InsertionSort
 * Package: SelectionSort
 *
 * @Author 马学兴
 * @Create 2023/11/29 20:35
 * @Version 1.0
 * Description:插入排序
 */
public class InsertionSort {
    private InsertionSort(){}
    public static  <E extends Comparable<E>> void sort(E[] arr){
        for (int i = 0; i < arr.length; i++) {
            //将arr[i]插入到合适位置
           /* for (int j = i; j -1>=0 ; j--) {
                if (arr[j].compareTo(arr[j-1])<0){
                    swap(arr,j,j-1);
                }else break;
            }*/
            for (int j = i; j -1>=0&&arr[j].compareTo(arr[j-1])<0 ; j--) {//第一次优化
                swap(arr,j,j-1);
            }

        }
    }
    public static  <E extends Comparable<E>> void sort2(E[] arr){
        for (int i = 0; i < arr.length; i++) {//正序从前往后
            E t=arr[i];//设置一个临时数组，第二次优化
            int j;
            for ( j = i; j -1>=0 && t.compareTo(arr[j-1])<0 ; j--) {
                arr[j]=arr[j-1];
            }
            arr[j]=t;

        }
    }
    public static  <E extends Comparable<E>> void sort3(E[] arr){
        for (int i = arr.length-1; i >=0; i--) {
            E t=arr[i];//设置一个临时数组
            int j;
            for ( j = i; j +1< arr.length && t.compareTo(arr[j+1])>0 ; j++) {
                arr[j]=arr[j+1];
            }
            arr[j]=t;

        }
    }
    private static <E>void swap(E[] arr,int i,int j){
        E t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }

    public static void main(String[] args) {
        int[] dataSize={1000,10000};
        for (int n:dataSize){//比较随机队列和有序队列的插入排序和选择排序速度
            System.out.println("Random Array:");
            Integer [] arr= ArrayGenerator.generateRandomArray(n,n);
            Integer [] arr2= Arrays.copyOf(arr,arr.length);//生成两个数组
            Integer [] arr3= Arrays.copyOf(arr,arr.length);//生成两个数组
            //SortingHelper.sortTest("InsertionSort",arr);
            SortingHelper.sortTest("InsertionSort2",arr2);
            SortingHelper.sortTest("SelectionSort",arr);
            SortingHelper.sortTest("InsertionSort3",arr3);

            System.out.println();
            System.out.println("Ordered Array:");//有序--证明插入排序遇到有序队列时间复杂度最快为O(1)
            arr=ArrayGenerator.generateOrderedArray(n);
            arr2=Arrays.copyOf(arr,arr.length);
            SortingHelper.sortTest("InsertionSort2",arr2);

            SortingHelper.sortTest("SelectionSort",arr);
            System.out.println();

        }
    }
}
